package com.lry.basic.algorithm.sort;

import static com.lry.basic.algorithm.sort.HeapSort.swap;

public class MaoPaoSort {


    public static void main(String[] args) {
        int [] arr = {7,1,2,3};
        maoPaoSort2(arr);
        for (int i :arr) {
            System.out.print(i+" ");
        }
    }

    //1 7 2 3
    //1 2 7 3
    //1 2 3 7
    private static void maoPaoSort(int [] arr){
        for(int i=0;i<arr.length;i++){
            for(int j=i+1;j<arr.length;j++){
                if(arr[i]>arr[j]){
                    swap(arr,i,j);
                }
            }
        }
    }

    // 3 2 1
    // 第一趟
    // 2 3 1
    // 2 1 3
    // 第二趟
    // 1 2 3
    private static void maoPaoSort1(int [] arr){
        for(int i=0;i<arr.length-1;i++){

            for(int j=0;j<arr.length-1-i;j++){
                if(arr[j]>arr[j+1]){
                    swap(arr,j,j+1);
                }
            }

        }
    }

    //1 2 3 5 4
    private static void maoPaoSort2(int [] arr){
        for(int i=0;i<arr.length-1;i++){
            boolean flag = false;
            for(int j=0;j<arr.length-1-i;j++){
                if(arr[j]>arr[j+1]){
                    swap(arr,j,j+1);
                    flag = true;
                }
            }
            //说明已经有序
            if(!flag){
                return;
            }
        }
    }

    private static void maoPaoSort3(int [] arr){
        int left = 0,right = arr.length-1;

        while(left<right){

            for(int i=left;i<right;i++){
                if(arr[i]>arr[i+1]){
                    swap(arr,i,i+1);
                }
            }
            right--;

            for(int j=right;j>left;j--){
                if(arr[j]<arr[j-1]){
                    swap(arr,j,j-1);
                }
            }
            left++;
        }

    }


    private static void maoPaoSort4(int [] arr){
        int left = 0,right = arr.length-1;
        int swapPos = left;

        while(left<right){

            for(int i=left;i<right;i++){
                if(arr[i]>arr[i+1]){
                    swap(arr,i,i+1);
                    swapPos = i;
                }
            }
            right = swapPos;

            for(int j=right;j>left;j--){
                if(arr[j]<arr[j-1]){
                    swap(arr,j,j-1);
                    swapPos = j;
                }
            }
            left = swapPos;
        }

    }



}
